package com.kingwood.algorithm.test;

import java.util.*;

/**
 * @Author 22025812
 * @Description: 图论 单源最短路径 Dijkstra
 * @Date: 2024/3/4 13:28
 * @Modified By：
 * @Version 1.0
 */
public class GraphDijkstra {

    /**
     * 电脑病毒感染
     * https://fcqian.blog.csdn.net/article/details/134386911
     * @param scanner
     * @return
     */
    public static int getMinTimeOfComputerVirus(Scanner scanner) {
        int n = scanner.nextInt(); // 电脑数量
        int m = scanner.nextInt(); // 数据量
        HashMap<Integer, ArrayList<int[]>> graph = new HashMap<>();

        for (int i=0; i<m; i++) {
            int u = scanner.nextInt();
            int v = scanner.nextInt();
            int w = scanner.nextInt();
            if (!graph.containsKey(u)) {
                graph.put(u, new ArrayList<>());
            }
            graph.get(u).add(new int[]{v, w});
        }

        // 记录源点到其他剩余的最短耗时
        int[] dist = new int[n + 1];
        // 初始时，假设源点不可达其他剩余点，即源点到达其他点的耗时无限大
        Arrays.fill(dist, Integer.MAX_VALUE);
        int src = scanner.nextInt();
        // 源点到达源点的耗时为0
        dist[src] = 0;

        boolean[] visited = new boolean[n + 1];

        // 优先队列needCheck中记录的其实是：已被探索过的路径的终点（路径指的是源点->终点）
        // 优先队列优先级规则是，路径终点的权重（即源点->终点的耗时）越小越优先
        PriorityQueue<Integer> needCheck = new PriorityQueue<>((a, b) -> dist[a] - dist[b]);
        // 初始被探索过的路径只有源点本身
        needCheck.add(src);

        while (!needCheck.isEmpty()) {
            // 取出最优路径的终点（耗时最少的路径）作为新的起点
            int cur = needCheck.poll();
            if (visited[cur]) {
                continue;
            }

            visited[cur] = true;
            for (int[] next : graph.get(cur)) {
                // v是可达的其他点，w是cur->v的耗时
                int v = next[0];
                int w = next[1];

                // 那么如果从源点到cur点的耗时是dist[cur]，那么源点到v点的耗时就是dist[cur] + w
                int newDist = dist[cur] + w;
                if (dist[v] > newDist) {
                    dist[v] = newDist;
                    needCheck.add(v);
                }
            }
        }

        // dist记录的是源点到达其他各点的最短耗时，我们取出其中最大的就是源点走完所有点的最短耗时
        int ans = 0;
        for (int i=1; i<=n; i++) {
            if (dist[i] == Integer.MAX_VALUE) {
                return -1;
            }
            ans = Math.max(ans, dist[i]);
        }

        return ans;
    }

    public static void main(String[] args) {
        Scanner scanner = new Scanner(System.in);
        System.out.println(getMinTimeOfComputerVirus(scanner));
    }
}
